算法（algorithm）是一组完成特定任务的有穷指令序列。
算法都必须满足以下标准：
- 输入：有零或多个由外部提供的输入量。
- 输出：至少产生一个输出量。
- 确定性：每条指令都有明确的语义。
- 有限性：算法的每一条执行路线都能在有限步之内结束。
- 有效性：每一条指令都必须足够简单，指令必须是可行的。
空间复杂性
对于程序 P，
-
固定的空间需求 \(c\)：与输入无关的空间需求。
如指令的存储空间，简单变量、固定大小的结构变量（结构体）和常量的存储空间。
-
可变的空间需求 \(S_P(I)\)：与实例 \(I\) 相关的空间需求。
对于算法来说，一个实例就是一组特定的输入参数。
空间复杂性 \(S(P)\) 是指程序从开始执行到完成所需的存储空间的数量。
$$S(P) = c + S_P(I)$$
在分析程序的空间复杂性时，通常只关心可变的空间需求 \(S_P(I)\)。
举例
【例一】：\(S_{sum}(n) = 0\)
float sum(float list[], int n)
{
float tempSum = 0;
for (int i = 0; i < n, i++)
tempSum += list[i];
return tempSum;
}
【例二】：\(S_{rsum}(n) \varpropto n\)
float rsum(float list[], int n)
{
if (n) return rsum(list, n-1) + list[n-1];
return 0;
}
这是因为每次迭代，均需要额外的栈上空间。
| 较早的帧 |
|---|
| --- 栈帧 Start --- |
| 被保存的 %ebp |
| 参数2 n |
| 参数1 list |
| 返回地址 |
| --- 栈帧 End --- |
| 被保存的 %ebp |
| ... |
每次调用都会产生如上的栈帧。迭代次数约为 n 次。
对于 i386，int（n） 占用 4 byte，指针（被保存的 %ebp、list、返回地址）占用 4 byte，所以 \(S_{rsum}(n) = 16n\) byte。
时间复杂性
程序 \(P\) 运行所需时间 \(T(P)\) 是其编译时间和执行时间的总和。
实际上，真正关注的只是程序的执行时间 \(T_P\)。
对于编译时间，一方面其与实例无关，另一方面编译好的程序可以多次执行，而不需再次编译。
程序步
程序步：
- 是一个有意义的程序片段；
- 执行时间必须与实例特征无关。
第 1 点中所谓的“有意义”可以理解为该片段会被执行。例如语句声明了一个未使用的变量，其在编译时会被忽略，即不会被执行，所以不能作为一个程序步。
将所有程序步分别乘以它们的执行次数，即可得到程序步数。可以使用程序步数来描述 \(T_P\)。
渐进记号
\(f(n) = O(g(n))\) 即表示 \(g(n)\) 是 \(f(n)\) 的同阶或高阶无穷大。
\(f(n) = \Omega(g(n))\) 即表示 \(g(n)\) 是 \(f(n)\) 的同阶或低阶无穷大。
\(f(n) = \Theta(g(n))\) 即表示 \(g(n)\) 是 \(f(n)\) 的同阶无穷大。
显然，如果 \(f(n) = a_mn^m + ... + a_1n + a_0\)，
则 \(f(n) = O(n^m)\);
若 \(a_m > 0\)，
则 \(f(n) = \Omega(n^m)\)，\(f(n) = \Theta(n^m)\)。
定义：
[BIG O] \(f(n) = O(g(n))\) 当且仅当存在正的常数 \(c\) 和 \(n_0\)，使得对于所有的 \(n\)，当 \(n \geq n_0\) 时，有 \(f(n) \leq cg(n)\)。
[\(\Omega\)] \(f(n) = \Omega(g(n))\) 当且仅当存在正的常数 \(c\) 和 \(n_0\)，使得对于所有的 \(n\)，当 \(n \geq n_0\) 时，有 \(f(n) \geq cg(n)\)。
[\(\Theta\)] \(f(n) = \Theta(g(n))\) 当且仅当存在正的常数 \(c_1\)，\(c_2\) 和 \(n_0\)，使得对于所有的 \(n\)，当 \(n \geq n_0\) 时，有 \(c_1g(n) \leq f(n) \leq c_2g(n)\)。
常用的g(n)
\(1, logn, n, nlogn, n^2, n^3, 2^n, n!\)
上面一行中，每个函数均是其左侧所有函数的高阶无穷大。
举例
【例一】折半查找的时间复杂性
while 循环最多迭代 \(\lceil log_2(n+1) \rceil\) 次。所以最坏情况下，该循环将迭代 \(\Theta(logn)\) 次。
int compare(int x, int y)
{
if (x < y) return -1;
else if (x < y) return 1;
else return 0;
}
int binsearch(int list[], int searchnum, int left, int right)
{
int middle;
while (left <= right) {
middle = (left + right)/2;
switch (compare(list[middle], searchnum)) {
case -1:
left = middle + 1;
break;
case 1:
right = middle - 1;
break;
case 0:
return middle;
}
}
return -1;
}
考虑最坏的情况，即在 left == right 时，才找到元素。
折半查找每次都会丢弃（大约）一半的元素。将查找过程反向考虑，则类似于一个 list 中元素增加的过程，每次“查找”均使 list 元素翻倍。
假设 list 中最初只有 1 个元素，经过 x 次“查找”，最终到达 n 个元素。则：\(2^x = n\)， 即 \(x = log_2(n)\)。
在此基础上，可以进一步考虑为什么 while 循环最多迭代 \(\lceil log_2(n+1) \rceil\) 次。
实际上，在这里我们并不那么关心具体的次数，具体的次数肯定是 \(log_2(n)\) 的同阶无穷大，即可得到 \(\Theta(logn)\)。
【例二】递归的全排列的时间复杂性
#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))
void perm(char *list, int i, int n)
{
int j, temp;
if (i == n) {
for (j = 0; j <= n; j++) {
printf("%c", list[j]);
}
printf(" ");
}
else {
for (j = i; j <= n; j++) {
SWAP(list[i], list[j], temp);
perm(list, i + 1, n);
SWAP(list[j], list[i], temp);
}
}
}
当 i == n 时，\(T_{perm}(i, n) = \Theta(n)\)；
当 i < n 时，\(T_{perm}(i, n) = (n - i + 1)T_{perm}(i + 1, n)\)，求解该递归方程，得 \(T_{perm}(i, n) = \Theta(n((n - i + 1)!))\)。
\(\dfrac{T(i, n)}{T(i + 1, n)}\dfrac{T(i + 1, n)}{T(i + 2, n)}...\dfrac{T(n - 2, n)}{T(n - 1, n)}\dfrac{T(n - 1, n)}{T(n, n)}\)
\(= \dfrac{T(i, n)}{T(n, n)} = \dfrac{T(i, n)}{\Theta(n)}\)
\(= (n - i + 1)(n - (i + 1) + 1)...(n - (n-2) + 1)(n - (n - 1) + 1)\)
\(= \dfrac{(n - i + 1)!}{2}\)
得 \(T_{perm}(i, n) = \Theta(n((n - i + 1)!))\)。
性能测量
利用程序生成最坏情况下的测试数据集，继而测试算法在最坏情况下的性能。
有时候利用程序生成最坏情况下的测试数据集也是非常困难的。
此时，对于关心的实例特征的一组取值，生成一个合适大小的测试数据集，得到在这些测试数据集上的运行时间，取最大值最为这组实例特征在最坏情况下的时间估计。